package cluster;

//import org.apache.log4j.Logger;

import geom.Vector;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

import org.grlea.log.SimpleLogger;


import processing.core.PApplet;

public class Duster<E extends Clusterable> implements Comparable{
	/**
	 * Logger for this class
	 */
	//private static final Logger logger = Logger.getLogger(Duster.class);

	private final SimpleLogger log = new SimpleLogger(Duster.class);
	protected static int nextID = 0;
	public int ID;
	
	public static enum DistMode{ CENTROID,LONGEST, SHORTEST, AVERAGE; }
	public static final DistMode distMode = DistMode.CENTROID;
	
	public enum HeightMode{ MAX, MIN, AVG };
	public static HeightMode defaultHeightMode = HeightMode.MAX; 
	
	public enum MergeMode{ MEAN, MEDIAN; }
	public static MergeMode defaultMergeMode = MergeMode.MEAN;

	public static LookupTable lookup; 
	public static boolean useLookup = true;
	
	public ArrayList<Duster<E>> children;
	public Duster<E> parent;
	public E centroid;
	public float maxDev;
	public float avgDev;
	public float minDist;
	public float maxDist;
	public float uniqueness;
	
	Duster<E> extreme1, extreme2;
	
	
	/*	--------------------------------------------------------------
	 * 	Clusterable Interface implementation
	 	--------------------------------------------------------------	*/
	
	@SuppressWarnings("unchecked")
	public Duster(E cent){
		ID = nextID++;
		centroid = (E)cent.getClone();
		maxDev = 0;
		avgDev = 0;
	}
	
	@SuppressWarnings("unchecked")
	public Duster(ArrayList<Duster<E>> children) throws InstantiationException, IllegalAccessException{
		ID = nextID++;
		if(children.size() < 1) return;
		centroid = (E) children.get(0).centroid.getClass().newInstance();
		addChildren(children);
	}
	
	@SuppressWarnings("unchecked")
	public Duster(Duster<E> d1, Duster<E> d2) throws InstantiationException, IllegalAccessException{
		ID = nextID++;
		addChild(d1, false);
		addChild(d2, false);
		centroid = (E) children.get(0).centroid.getClass().newInstance();
		calcCentroid();
		calcMaxDev();
		calcMaxMinDist();
		uniqueness = getLocalUniqueness();
	}
	
	public int getID(){
		return ID;
	}
	/*	--------------------------------------------------------------
	 * 	relations
	 	--------------------------------------------------------------	*/
	
	public enum Relation{isChildOf, isParentOf, isSiblingOf, other, same;}
	
	public Duster<E> getRoot(){
		if(isRoot())return this;
		else return parent.getRoot();
	}
	
	public Relation getRelationTo(Duster<E> d){
		int[] thisP = getPosition();
		int[] dP = d.getPosition();
		int splits = 0;
		for(int i = 0; i < Math.min(thisP.length, dP.length); i++){
			if(thisP[i] != dP[i]) splits++;
		}
		if(thisP.length == dP.length){
			if(splits == 0) return Relation.same;
			if(splits == 1) return Relation.isSiblingOf;
		}
		if(splits == 0){
			if(thisP.length > dP.length) return Relation.isChildOf;
			if(thisP.length < dP.length) return Relation.isParentOf;
		}
		return Relation.other;
	}
	
	public int[] getPosition(){
		return getPoisition(new int[]{parent.children.indexOf(this)});
	}
	
	private int[] getPoisition(int[] p){
		if(isRoot()) return p;
		int[] rp = new int[p.length+1];
		rp[0] = parent.children.indexOf(this);
		for (int i = 0; i < p.length; i++) {
			rp[i+1] = p[i];
		}
		return parent.getPoisition(rp);
	}
	
	
	
	/*	--------------------------------------------------------------
	 * 	modification
	 	--------------------------------------------------------------	*/
	private void setParent(Duster<E> p){
		parent = p;
		
	}
	public void addChild(Duster<E> d) { addChild(d, true); }
	public void addChild(Duster<E> d, boolean update){
		//log.entry("addChild(Duster<E> d)");
		if(children == null) children = new ArrayList<Duster<E>>();
		d.setParent(this);
		children.add(d);
		if(update){
			calcCentroid();
			calcMaxDev();
			calcMaxMinDist();
			uniqueness = getLocalUniqueness();
		}
	}
	public void addChildren(ArrayList<Duster<E>> c){ addChildren(c, true); }
	public void addChildren(ArrayList<Duster<E>> c, boolean update){
		//log.entry("addChildren(ArrayList<Duster<E>> c)");
		if(children == null) children = new ArrayList<Duster<E>>();
		Iterator<Duster<E>> cdi = c.iterator();
		while(cdi.hasNext()){
			Duster<E> d = cdi.next();
			d.setParent(this);
			addChild(d, false);
		}
		if(update){
			calcCentroid();
			calcMaxDev();
			calcMaxMinDist();
			uniqueness = getLocalUniqueness();
		}
	}
	
	public void assimilateChildren(){
		for(int i =  children.size(); i >= 0; i--)
			assimilateChild(i);
	}
	
	public void assimilateOffspring(){
		ArrayList<Duster<E>> leafs = getLeafs();
		children = new ArrayList<Duster<E>>();
		addChildren(leafs);
	}
	/*
	public void mergeChildren(ArrayList<Duster<E>> list) throws InstantiationException, IllegalAccessException{
		ArrayList<Duster<E>> d = new ArrayList<Duster<E>>();
		Iterator<Duster<E>> i = list.iterator();
		while(i.hasNext()){
			Duster<E> next = i.next();
			children.remove(next);
			if(next.isLeaf()) d.add(next);
			else d.addChildren(next.children);
		}
		addChild(new Duster<E>(d));
	}
	*/
	public ArrayList<Duster<E>> getClosestChildren(){
		Duster<E> d1=null, d2=null, cd1=null, cd2=null;
		float minDist = Float.MAX_VALUE;
		Iterator<Duster<E>> i1 = children.iterator();
		Iterator<Duster<E>> i2;
		while(i1.hasNext()){
			d1 = i1.next();
			i2 = children.iterator();
			while(i2.hasNext()){
				d2 = i2.next();
				float dist = d1.getDistanceTo(d2);
				if(dist < minDist){
					cd1 = d1;
					cd2 = d2;
					minDist = dist;
				}
			}
		}
		if(cd1 == null || cd2 == null) return null;
		ArrayList<Duster<E>> ret = new ArrayList<Duster<E>>();
		ret.add(cd1);
		ret.add(cd2);
		return ret;
	}
	
	public void assimilateChild(Duster<E> d){ 
		assimilateChild(children.indexOf(d)); 
	}
	@SuppressWarnings("unchecked")
	public void assimilateChild(int i){
		if(i >= children.size()) return;
		if(children.get(i).isLeaf()) return;
		if(useLookup) lookup.removeDuster(children.get(i));
		Duster<E> assimilated = children.remove(i);
		addChildren(assimilated.children);
	}

	public void convertToLeaf(){ convertToLeaf(defaultMergeMode); }
	@SuppressWarnings("unchecked")
	public void convertToLeaf(MergeMode mm){
		if(isLeaf()) return;
		if(useLookup){
			if(lookup != null){
				Iterator<Duster<E>> i = children.iterator();
				while(i.hasNext()) lookup.removeDuster(i.next());
			}
		}
		switch(mm){
		case MEAN: children = null; break;
		case MEDIAN: 
			centroid = getMedian().centroid;
			children = null;
			break;
		}
	}
	
	public Duster<E> getBlackSheep(){
		if(isLeaf()) return null;
		Iterator<Duster<E>> i1 = children.iterator();
		Iterator<Duster<E>> i2;
		float maxDist = 0;
		Duster<E> blackSheep = null;
		while(i1.hasNext()){
			Duster<E> c1 = i1.next();
			i2 = children.iterator();
			float totalDist = 0;
			while(i2.hasNext()){
				Duster<E> c2 = i2.next();
				if(!c1.equals(c2));
					totalDist += c2.getDistanceTo(c1);
			}
			if(totalDist > maxDist){
				blackSheep = c1;
				maxDist = totalDist;
			}
		}
		return blackSheep;
	}

	
	
	
	/*	--------------------------------------------------------------
	 * 	Navigation
	 	--------------------------------------------------------------	*/
	

	
	public Duster<E> getParent(){
		//log.entry("getParent()");
		return parent;
	}
	
	public Duster<E> getNextSibling(){
		//log.entry("nextSibling()");
		if(isRoot()) return this;
		int index = (parent.getChildren().indexOf(this)+1) % getParent().getChildren().size();
		return getParent().getChild(index);
		
	}
	public Duster<E> getPrevSibling(){
		log.entry("prevSibling()");
		if(isRoot()) return this;
		int index = (getParent().getChildren().indexOf(this)-1);
		while(index < 0) index = getParent().getChildren().size() - index;
		return getParent().getChild(index);
	}
	
	public Duster<E> getChild(int i){
		log.entry("getChild(int i)");
		return children.get(i);
	}
	
	public ArrayList<Duster<E>> getChildren(){
		//log.entry("getChildren()");
		return children;
	}
	
	public ArrayList<Duster<E>> getAllChildren(){
		ArrayList<Duster<E>> offspring = new ArrayList<Duster<E>>();
		if(isLeaf()) offspring.add(this);
		else{
			Iterator<Duster<E>> i = children.iterator();
			while(i.hasNext()) offspring.addAll(i.next().getAllChildren());
		}
		return offspring;
	}
	
	public ArrayList<Duster<E>> getOffspring(int targetLevel){
		return getOffspring(targetLevel, 0);
	}
	
	private ArrayList<Duster<E>> getOffspring(int targetLevel, int level){
		ArrayList<Duster<E>> offspring = new ArrayList<Duster<E>>();
		if(level == targetLevel){
			offspring.add(this);
		}
		else if(!isLeaf()){
			level++;
			Iterator<Duster<E>> i = children.iterator();
			while(i.hasNext()) offspring.addAll(i.next().getOffspring(targetLevel, level));
		}
		else if(isLeaf()){
			offspring.add(this);
		}
		return offspring;
	}
	
	public void assimilateOffspringBelow(int generation){
		ArrayList<Duster<E>> offspring = new ArrayList<Duster<E>>();
		Iterator<Duster<E>> i = children.iterator();
		while(i.hasNext()) offspring.addAll(i.next().getOffspringBelow(generation));
		children = new ArrayList<Duster<E>>();
		addChildren(offspring);
	}

	
	public ArrayList<Duster<E>> getOffspringBelow(int generation){
		ArrayList<Duster<E>> offspring = new ArrayList<Duster<E>>();
		if(generation <= getHeight()) offspring.add(this);
		else{
			if(!isLeaf()){
				Iterator<Duster<E>> i = children.iterator();
				while(i.hasNext()) offspring.addAll(i.next().getOffspringBelow(generation));
			}
		}
		return offspring;
	}
	
	public ArrayList<Duster<E>> getPredesessors(int generations){
		ArrayList<Duster<E>> foreFathers = new ArrayList<Duster<E>>();
		if(generations == getHeight()) foreFathers.add(this);
		else{
			if(!isLeaf()){
				Iterator<Duster<E>> i = children.iterator();
				while(i.hasNext()) foreFathers.addAll(i.next().getPredesessors(generations));
			}
 		}
		return foreFathers;
	}
	
	public float getLocalUniqueness(){
		if(isRoot()) return 1;
		Iterator<Duster<E>> i = parent.children.iterator();
		float uniq = 1;
		while(i.hasNext()){
			Duster<E> next = i.next();
			if(next != this){
				float dist = getDistanceTo(next);
				uniq -= Math.pow(dist / 200f, 3) / children.size(); 
			}
		}
		return uniq;
	}
	
	public Duster<E> getHighestChild(){
		Iterator<Duster<E>> i = children.iterator();
		float maxH = -1;
		Duster<E> highest = null;
		while(i.hasNext()){
			Duster<E> next = i.next();
			int height = next.getHeight();
			if(height > maxH){
				maxH = height;
				highest = next;
			}
		}
		return highest;
		
	}
	
	
	
	/*	--------------------------------------------------------------
	 * 	Orientation Finding methods
	 	--------------------------------------------------------------	*/
	
	public boolean isRoot(){
		//log.entry("isRoot()");
		return getParent() == null;
	}
	
	public boolean isLeaf(){
		//log.entry("isLeaf()");
		return getChildren() == null || getChildren().size() == 0;
	}
	

	
	public int getHeight(){
		return getHeight(0, defaultHeightMode);
	}
	public int getHeight(HeightMode mode){
		return getHeight(0, mode);
	}
	
	private int getHeight(int level, HeightMode mode){
		log.entry("getHeight(int level, DepthMode mode)");
		if(isLeaf()){
			log.exit("getHeight(int level, DepthMode mode(leaf))");
			return level;
		}
		else{
			level++;
			Iterator<Duster<E>> i = children.iterator();
			float height = 0;
			if(mode == HeightMode.MIN) height = Integer.MAX_VALUE;
			while(i.hasNext()) {
				int high = i.next().getHeight(level, mode);
				switch(mode){
				case MAX: if(high > height) height = high; break;
				case MIN: if(high < height) height = high; break;
				case AVG: height += high; break;
				}
			}
			if(mode == HeightMode.AVG) height = Math.round(height / children.size());
			log.exit("getHeight(int level, DepthMode mode)");
			return (int)height;
		}
		
	}
	
	public int getDepth(){
		return getDepth(0);
	}
	
	private int getDepth(int lvl){
		if(isRoot())
			return lvl;
		else{
			lvl++;
			return getParent().getDepth(lvl);
		}
	}
	
	public float getMaxDev(){
		return maxDev;
	}
	
	public float getAvgDev(){
		return avgDev;
	}
	
	
	
	public ArrayList<Duster<E>> getLeafs(){
		ArrayList<Duster<E>> ret = new ArrayList<Duster<E>>();
		//log.entry("getAllChildren()");
		if(isLeaf()) ret.add(this);
		else{
			Iterator<Duster<E>> i = children.iterator();
			while(i.hasNext()) ret.addAll(i.next().getLeafs());
		}
		return ret;
	}
	
	public ArrayList<E> convertToCentroids(ArrayList<Duster<E>> list){
		ArrayList<E> centroids = new ArrayList<E>();
		Iterator<Duster<E>> i = list.iterator();
		while(i.hasNext())
			centroids.add(i.next().centroid);
		return centroids;
	}
	
	
	/*	--------------------------------------------------------------
	 * 	Metrics
	 	--------------------------------------------------------------	*/

	@SuppressWarnings("unchecked")
	private void calcCentroid(){
		if(isLeaf()) return;
		ArrayList<Duster<E>> leafs = getLeafs();
		ArrayList<E> centroids = convertToCentroids(leafs);
		centroid = (E)centroid.newEmpty();
		centroid.setCentroid(centroids);
	}
	
	private void calcMaxDev(){
		Iterator<Duster<E>> leafs = getLeafs().iterator();
		float maxDist = 0;
		float avgDist = 0;
		int count = 0;
		while(leafs.hasNext()){
			float dist = centroid.distanceTo(leafs.next().centroid);
			avgDist += dist;
			if(dist > maxDist)
				maxDist = dist;
			count++;
		}
		maxDev = maxDist;
		avgDev = avgDist / count;
	}
	
	private void calcMaxMinDist(){
		Iterator<Duster<E>> i1 = children.iterator();
		Iterator<Duster<E>> i2;
		float maxDist = 0;
		float minDist = Float.MAX_VALUE;
		Duster<E> ld1 = null, ld2 = null;
		while(i1.hasNext()){
			i2 = children.iterator();
			Duster<E> d = i1.next();
			while(i2.hasNext()){
				Duster<E> d2 = i2.next();
				float dist = d.longestDistance(d2);
				if(dist > maxDist) {
					maxDist = dist;
					ld1 = d;
					ld2 = d2;
				}
				if(dist < minDist) minDist = dist;
				
			}
		}
		this.maxDist = maxDist;
		this.minDist = minDist;
		Vector sortVector = ld1.centroid.getDirectionVector(ld2.centroid);
		i1 = children.iterator();
		while(i1.hasNext()) i1.next().centroid.setSortVector(sortVector);
		extreme1 = ld1;
		extreme2 = ld2;
		
	}

	public Duster<E> getMedian(){
		Iterator<Duster<E>> leafs = getLeafs().iterator();
		float minDist = Float.MAX_VALUE;
		Duster<E> median = null;
		while(leafs.hasNext()){
			Duster<E> current = leafs.next();
			float dist = averageDistance(current);
			if(dist < minDist){
				minDist = dist;
				median = current;
			}
		}
		return median;
	}

	

	
	public float getDistanceTo(Duster<E> d){
		if(ID == d.ID) return Float.NaN;
		float dist = Float.MAX_VALUE;
		switch(distMode){
			case CENTROID: dist = centroidDistance(d); break;
			case SHORTEST: dist = shortestDistance(d); break;
			case AVERAGE: dist = averageDistance(d); break;
			case LONGEST: dist = longestDistance(d); break;
			default: dist = centroidDistance(d); break;
		}
		if(dist == 0 || dist == Float.MAX_VALUE)
			log.info("noGood: " + centroid.toString() + " ::: " + d.centroid.toString());
		
		return dist;
	}
	private float distanceToLongestLine(Duster<E> b){
		if(isLeaf()) return centroidDistance(b);
		Vector l1 = extreme1.centroid.getVector();
		Vector l2 = extreme2.centroid.getVector();
		Vector l = l2.sub(l1);
		Vector p = b.centroid.getVector();
		float r = p.sub(l1).dotProduct(p.sub(l2)) / l.absLength();
		if(r >= 0 && r <= 1){
			Vector dp = l1.add(l.mult(r));
			return p.sub(dp).absLength();
		}
		else if(r < 0) return p.sub(l1).absLength();
		else return p.sub(l2).absLength();
	}
	
	
	private float centroidDistance(Duster<E> b){
		float dist;
		if(useLookup && lookup != null){
			dist = lookup.getDistance(this, b);
			if(Float.isNaN(dist)){
				dist = centroid.distanceTo(b.centroid);
				//lookup.addDistance(this, b, dist);
			}
			return dist;
		}
		else return centroid.distanceTo(b.centroid);
		
	}
	
	private float longestDistance(Duster<E> b){
		float dist;
		if(useLookup && lookup != null){
			dist = lookup.getDistance(this, b);
			if(!Float.isNaN(dist)){				
				return dist;
			}
		}
		if(this.isLeaf() && b.isLeaf()) return centroidDistance(b);
		float longest = 0;
		if(isLeaf()){
			Iterator<Duster<E>> ib = b.getLeafs().iterator();
			while(ib.hasNext()){
				dist = centroidDistance(ib.next());
				if(dist > longest)
					longest = dist;
			}
		}
		else if(b.isLeaf()){
			Iterator<Duster<E>> ia = getLeafs().iterator();
			while(ia.hasNext()){
				dist = b.centroidDistance(ia.next());
				if(dist > longest)
					longest = dist;
			}
		}
		else{
			Iterator<Duster<E>> ia = this.getLeafs().iterator();
			while(ia.hasNext()){
				Duster<E> current = ia.next();
				Iterator<Duster<E>> ib;
				ib = b.getLeafs().iterator();
				while(ib.hasNext()){
					dist = current.centroidDistance(ib.next());
					if(dist > longest)
						longest = dist;
				}
			}
		}
		//if(useLookup && lookup != null)lookup.addDistance(this, b, longest);
		return longest;
	}
	
	private float shortestDistance(Duster<E> b){
		float dist;
		if(useLookup && lookup != null){
			dist = lookup.getDistance(this, b);
			if(!Float.isNaN(dist)){
				return dist;
			}
		}
		if(isLeaf() && b.isLeaf()) return centroidDistance(b);
		float shortest = Float.MAX_VALUE;
		if(isLeaf()){
			Iterator<Duster<E>> ib = b.getLeafs().iterator();
			while(ib.hasNext()){
				dist = centroid.distanceTo(ib.next().centroid);
				if(dist < shortest)
					shortest = dist;
			}
		}
		else if(b.isLeaf()){
			Iterator<Duster<E>> ia = getLeafs().iterator();
			while(ia.hasNext()){
				dist = b.centroidDistance(ia.next());
				if(dist < shortest)
					shortest = dist;
			}
		}
		else{
			Iterator<Duster<E>> ia = getLeafs().iterator();
			while(ia.hasNext()){
				Duster<E> current = ia.next();
				Iterator<Duster<E>> ib;
				ib = b.getLeafs().iterator();
				while(ib.hasNext()){
					dist = current.centroidDistance(ib.next());
					if(dist < shortest)
						shortest = dist;
				}
			}
		}
		//if(useLookup)lookup.addDistance(this, b, shortest);
		return shortest;
	}
	
	private float averageDistance(Duster<E> b){
		float dist;
		if(useLookup && lookup != null){
			dist = lookup.getDistance(this, b);
			if(!Float.isNaN(dist)){
				return dist;
			}
		}
		if(isLeaf() && b.isLeaf()) return centroidDistance(b);
		float total = 0;
		if(isLeaf()){
			Iterator<Duster<E>> ib = b.getLeafs().iterator();
			while(ib.hasNext()){
				total += centroid.distanceTo(ib.next().centroid);
			}
			total /= b.getLeafs().size();
		}
		else if(b.isLeaf()){
			Iterator<Duster<E>> ia = getLeafs().iterator();
			while(ia.hasNext()){
				total += b.centroidDistance(ia.next());
			}
			total /= getLeafs().size();
		}
		else{
			Iterator<Duster<E>> ia = getLeafs().iterator();
			while(ia.hasNext()){
				Duster<E> current = ia.next();
				Iterator<Duster<E>> ib;
				ib = b.getLeafs().iterator();
				while(ib.hasNext()){
					total += current.centroidDistance(ib.next());
				}
			}
			total /= (getLeafs().size() * b.getLeafs().size());
		}
		//lookup.addDistance(this, b, total);
		return total;
	}
	float x, y, w, h;
	public void setDrawRect(float x, float y, float w, float h){
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
	}
	public boolean selected;
	public void draw(PApplet pa){
		centroid.draw(pa, x, y, w, h, selected);
		if(!isLeaf()) {
			Iterator<Duster<E>> ci = children.iterator();
			while(ci.hasNext()) ci.next().draw(pa);
		}
	}
	public Duster<E> contains(float x, float y){
		if(this.x <= x && this.x + w >= x && this.y <= y && this.y + h >= y) return this;
		if(!isLeaf()) {
			Iterator<Duster<E>> ci = children.iterator();
			while(ci.hasNext()){
				Duster<E> d = ci.next().contains(x, y);
				if(d != null) return d;
			}
		}
		return null;
	}

	@SuppressWarnings("unchecked")
	public int compareTo(Object arg0) {
		return centroid.compareTo(((Duster<E>)arg0).centroid);
	}
	
	public void sortAll(){
		if(isLeaf()) return;
		Collections.sort(children);
		Iterator<Duster<E>> i = children.iterator();
		while(i.hasNext()) i.next().sortAll();
	}


	
	
}
